package G1;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

public class ArrayList<E>
extends	AbstractList<E> implements	List<E>{
	private transient Object[]	elementData;
	private int size;
	public	ArrayList(int	initialCapacity) {
		super();
		if	(initialCapacity < 0)
			throw new IllegalArgumentException("Illegal Capacity: "+
					initialCapacity);
		this.elementData	=	new	Object[initialCapacity];
	}

	public	ArrayList()	{
		this(20);
	}
	public	ArrayList(Collection<? extends E>	c) {
		elementData = c.toArray();
		size	=	elementData.length;
		if	(elementData.getClass()	!= Object[].class)
			elementData = Arrays.copyOf(elementData,	size,	Object[].class);
	}
	public	void trimToSize()	{
		modCount++;
		int oldCapacity = elementData.length;
		if	(size	<	oldCapacity) {
			elementData = Arrays.copyOf(elementData,	size);
		}
	}

	public	void ensureCapacity(int	minCapacity) {
		if	(minCapacity > 0)
			ensureCapacityInternal(minCapacity);
	}

	private void	ensureCapacityInternal(int minCapacity)	{
		modCount++;
		if	(minCapacity - elementData.length	>	0)
			grow(minCapacity);
	}
	private static	final	int	MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

	private void	grow(int minCapacity)	{
		int oldCapacity = elementData.length;
		int newCapacity = oldCapacity + (oldCapacity	>> 1);
		if	(newCapacity - minCapacity < 0)
			newCapacity = minCapacity;
		if	(newCapacity - MAX_ARRAY_SIZE	>	0)
			newCapacity = hugeCapacity(minCapacity);
		elementData = Arrays.copyOf(elementData,	newCapacity);
	}

	private static	int	hugeCapacity(int minCapacity)	{
		if	(minCapacity < 0)	// overflow
			throw new OutOfMemoryError();
		return	(minCapacity > MAX_ARRAY_SIZE) ?
				Integer.MAX_VALUE :
					MAX_ARRAY_SIZE;
	}

	public	int	size() {
		return	size;
	}

	public	boolean	isEmpty()	{
		return	size ==	0;
	}
	public	boolean	contains(Object	o) {
		return	indexOf(o) >=	0;
	}
	public	int	indexOf(Object o)	{
		if	(o ==	null)	{
			for (int	i	=	0; i < size; i++)
				if	(elementData[i]==null)
					return	i;
		} else	{
			for (int	i	=	0; i < size; i++)
				if	(o.equals(elementData[i]))
					return	i;
		}
		return	-1;
	}

	public	int	lastIndexOf(Object o)	{
		if	(o ==	null)	{
			for (int	i	=	size-1;	i	>= 0;	i--)
				if	(elementData[i]==null)
					return	i;
		} else	{
			for (int	i	=	size-1;	i	>= 0;	i--)
				if	(o.equals(elementData[i]))
					return	i;
		}
		return	-1;
	}
	E elementData(int index) {
		return (E) elementData[index];
	}

	public	Object[] toArray() {
		return	Arrays.copyOf(elementData, size);
	}

	public void swap(int i, int j){
		E temp=(E) elementData[i];
		elementData[i] = elementData[j];
		elementData[j] = temp; 
	}
	public	E	get(int	index) {
		rangeCheck(index);
		return	elementData(index);
	}


	public	E	set(int	index, E element)	{
		rangeCheck(index);

		E oldValue	=	elementData(index);
		elementData[index]	=	element;
		return	oldValue;
	}
	public	boolean	add(E	e) {
		ensureCapacityInternal(size + 1);	// Increments	modCount!!
		elementData[size++] = e;
		return	true;
	}
	public	boolean	append(E	e) {
		 elementData[size-1] += (String) e;
		return	true;
	}
	public	void add(int index,	E	element) {
		rangeCheckForAdd(index);

		ensureCapacityInternal(size + 1);	// Increments	modCount!!
		System.arraycopy(elementData, index,	elementData, index + 1,
				size - index);
		elementData[index]	=	element;
		size++;
	}
	public	E	remove(int index)	{
		rangeCheck(index);

		modCount++;
		E oldValue	=	elementData(index);

		int numMoved	=	size - index - 1;
		if	(numMoved	>	0)
			System.arraycopy(elementData, index+1,	elementData, index,
					numMoved);
		elementData[--size] = null; 

		return	oldValue;
	}
	private void fastRemove(int index) {
		modCount++;
		int numMoved = size - index - 1;
		if (numMoved > 0)
			System.arraycopy(elementData, index+1, elementData, index,
					numMoved);
		elementData[--size] = null; 
	}

	public	boolean	remove(Object	o) {
		if	(o ==	null)	{
			for (int	index	=	0; index < size; index++)
				if	(elementData[index]	== null) {
					fastRemove(index);
					return	true;
				}
		} else	{
			for (int	index	=	0; index < size; index++)
				if	(o.equals(elementData[index])) {
					fastRemove(index);
					return	true;
				}
		}
		return	false;
	}

	public	void clear() {
		modCount++;
		for (int	i	=	0; i < size; i++)
			elementData[i]	=	null;

		size	=	0;
	}
	public	boolean	addAll(Collection<?	extends	E> c)	{
		Object[]	a	=	c.toArray();
		int numNew	=	a.length;
		ensureCapacityInternal(size + numNew);	 //	Increments modCount
		System.arraycopy(a, 0,	elementData, size, numNew);
		size	+= numNew;
		return	numNew !=	0;
	}

	public	boolean	addAll(int index,	Collection<? extends E>	c) {
		rangeCheckForAdd(index);

		Object[]	a	=	c.toArray();
		int numNew	=	a.length;
		ensureCapacityInternal(size + numNew);	 //	Increments modCount

		int numMoved	=	size - index;
		if	(numMoved	>	0)
			System.arraycopy(elementData, index,	elementData, index + numNew,
					numMoved);

		System.arraycopy(a, 0,	elementData, index,	numNew);
		size	+= numNew;
		return	numNew !=	0;
	}

	protected void	removeRange(int	fromIndex, int toIndex)	{
		modCount++;
		int numMoved	=	size - toIndex;
		System.arraycopy(elementData, toIndex,	elementData, fromIndex,
				numMoved);

		int newSize = size	-	(toIndex-fromIndex);
		while (size !=	newSize)
			elementData[--size] = null;
	}

	private void	rangeCheck(int index)	{
		if	(index >=	size)
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}
	private void	rangeCheckForAdd(int index)	{
		if	(index > size	|| index < 0)
			throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}
	private String	outOfBoundsMsg(int index)	{
		return	"Index:	"+index+", Size: "+size;
	}
	public	boolean	removeAll(Collection<?>	c) {
		return	batchRemove(c, false);
	}

	private boolean batchRemove(Collection<?> c,	boolean	complement)	{
		final Object[]	elementData	=	this.elementData;
		int r = 0,	w	=	0;
		boolean modified	=	false;
		try {
			for (;	r	<	size;	r++)
				if	(c.contains(elementData[r])	== complement)
					elementData[w++]	=	elementData[r];
		} finally {
			if	(r !=	size)	{
				System.arraycopy(elementData, r,
						elementData, w,
						size - r);
				w +=	size - r;
			}
			if	(w !=	size)	{
				for (int	i	=	w; i < size; i++)
					elementData[i]	=	null;
				modCount	+= size	-	w;
				size	=	w;
				modified	=	true;
			}
		}
		return	modified;
	}


}